package fun.coding.leetcode;

public class ConvertSortedListToBinarySearchTree {

	// https://oj.leetcode.com/problems/convert-sorted-list-to-binary-search-tree/
	public static void main(String[] args) {
		// 3->5->8
		ConvertSortedListToBinarySearchTree csltbst = new ConvertSortedListToBinarySearchTree();
		ListNode head = new ListNode(3);
		ListNode l1 = new ListNode(5);
		ListNode l2 = new ListNode(8);
		head.next = l1;
		l1.next = l2;
		
		TreeNode root = csltbst.sortedListToBST(head);
		System.out.println(root.val);
		
	}
	
	// The reason to keep this private list is the same as header, if we pass in this value, 
	// it won't increase since it is pass by value, so reference holds the same
	private ListNode cur;
	
	public TreeNode sortedListToBST(ListNode head) {
		// Doesn't matter if pass t or head, it is all pass by value, so the reference will not change in this function
		// Just like if you pass in an integer
		ListNode t = head;
		int n = getListSize(t);
		if (n == 0) return null;
		
		this.cur = head;
		return helper(0, n - 1);
	}
	
	// in order manner
	public TreeNode helper(int start, int end) {
		if (start > end) return null;
		
		int mid = start + (end-start) / 2;
		
		TreeNode left = helper(start, mid - 1);
		TreeNode root = new TreeNode(cur.val);
		root.left = left;
		// if helper(ListNode cur, start, end) cur = cur.next, won't work
		this.cur = this.cur.next;
		root.right = helper(mid + 1, end);
		
		return root;
	}
	
	private int getListSize(ListNode head) {
		int size = 0;
		
		while (head != null) {
			head = head.next;
			size++;
		}
		return size;
	}
}
